#include <iostream>
#include <unordered_map>
using namespace std;

class LRUCache{
private:
    class Node {
    public:
      int val;
      int key;
      Node *prev;
      Node *next;
      Node():val(-1), prev(NULL), next(NULL){}
    };
    int capacity;
    int count;
    unordered_map<int, Node> store;
    Node *lastUpdate;
    Node *oldestUpdate;
public:
    LRUCache(int capacity) {
        this->capacity = capacity;
        lastUpdate = NULL;
        oldestUpdate = NULL;
        count = 0;
    }
    
    int get(int key) {
        if(this->store[key].val > 0){
			Node *change = &store[key];
			if (lastUpdate != change && oldestUpdate != change) {
            	change->next->prev = change->prev;
		        change->prev->next = change->next;
	            change->prev = lastUpdate;
	            change->next = NULL;
	            lastUpdate->next = change;
	            lastUpdate = change;
			} else if (lastUpdate != change && oldestUpdate == change) {
				oldestUpdate = oldestUpdate->next;
				oldestUpdate->prev = NULL;
				change->next = NULL;
				change->prev = lastUpdate;
				lastUpdate->next = change;
				lastUpdate = change;
			}
            return this->store[key].val;
        } else {
			store.erase(key);
            return -1;
        }
    }
    
    void set(int key, int value) {
        if(this->store[key].val < 0){
            if (count < capacity){
                this->store[key].val = value;
				this->store[key].key = key;
                Node *newNode = &store[key];
                newNode->prev = lastUpdate;
                newNode->next = NULL;
				if(this->lastUpdate == NULL){
					this->lastUpdate = newNode;
					this->oldestUpdate = newNode;
				} else {
                	this->lastUpdate->next = newNode;
	                this->lastUpdate = newNode;
				}
	            count++;
            } else {
                int vim = oldestUpdate->key;
                oldestUpdate = oldestUpdate->next;
				if (oldestUpdate != NULL) {
					oldestUpdate->prev->next = NULL;
                	oldestUpdate->prev = NULL;
				}
                store.erase(vim);
				
                this->store[key].val = value;
                this->store[key].key = key;
                Node *newNode = &store[key];
                newNode->prev = lastUpdate;
                newNode->next = NULL;
				if(lastUpdate == NULL){
					lastUpdate = newNode;
					oldestUpdate = newNode;
				} else {
                	lastUpdate->next = newNode;
	               	lastUpdate = newNode;
				}
            }
        } else {
            this->store[key].val = value;
            Node *change = &store[key];
			if (lastUpdate != change && oldestUpdate != change) {
            	change->next->prev = change->prev;
		        change->prev->next = change->next;
	            change->prev = lastUpdate;
	            change->next = NULL;
	            lastUpdate->next = change;
	            lastUpdate = change;
			} else if (lastUpdate != change && oldestUpdate == change) {
				oldestUpdate = oldestUpdate->next;
				oldestUpdate->prev = NULL;
				change->next = NULL;
				change->prev = lastUpdate;
				lastUpdate->next = change;
				lastUpdate = change;
			}
        }
    }
	void display(){
		 for ( auto it = store.begin(); it != store.end(); ++it )
    		cout << " " << it->first << ":" << it->second.val;
  		cout << endl;
	}
};

int main(){
	LRUCache cache(2);
	cache.set(2, 1);
	cache.set(1, 1);
	cache.get(2);
	cache.set(4, 1);
	cout<<cache.get(1)<<" "<<cache.get(2)<<endl;
	cache.display();
	return 0;
}














